// 左边浅，右边深   左单旋

// 左单旋时：
/*	    旋转节点: 当前不平衡的节点                          2                           5
		新根： 右子树的根节点                                  5        ==》         2    6
		变化分支：旋转节点的右子树的左子树                    3      6                   3
		不变分支：旋转节点的右子树的右子树
*/


//右单旋
/*      旋转节点: 当前不平衡的节点                            6                          5
*       新根： 左子树的根节点                             5             ==》         2      6
*       变化分支：旋转节点的左子树的右子树                2    3                             3
*       不变分支：旋转节点的左子树的左子树
* */


function Node(value) {
	this.value = value;
	this.left = null;
	this.right = null;
}

var node2 = new Node("2");
var node5 = new Node("5");
var node3 = new Node("3");
var node6 = new Node("6");


node2.right = node5
node5.left = node3
node5.right = node6

function getDeep(root) {
	if (root === null) return 0
	let leftDeep = getDeep(root.left)
	let rightDeep = getDeep(root.right)
	return Math.max(leftDeep, rightDeep) + 1
}

function isBalance(root) {
	if (root == null) return true
	let leftDeep = getDeep(root.left)
	let rightDeep = getDeep(root.right)
	if (Math.abs(leftDeep - rightDeep) > 1) { //两树的绝对值 > 1  不平衡
		return false
	} else {
		return isBalance(root.left) && isBalance(root.right)
	}
}

function leftRotate(root) {
	var newRoot = root.right  //找到新根
	var changeTree = root.right.left        //变化分支
	root.right = changeTree  //旋转节点的有孩子为变化分支
	newRoot.left = root     //新根的左孩子为旋转节点
	return newRoot
}

function rightRotate(root) {
	var newRoot = root.left
	root.left = root.left.right
	newRoot.right = root
	return newRoot
}

function change(root) {         //返回平衡后的根节点
	if (isBalance(root)) return root
	if (root.left !== null) root.left = change(root.left)
	if (root.right !== null) root.right = change(root.right)
	var leftDeep = getDeep(root.left)
	var rightDeep = getDeep(root.right)
	if (Math.abs(leftDeep - rightDeep) < 2) {
		return true
	} else if (leftDeep > rightDeep) {    //不平衡  左边深  右旋
		return rightRotate(root)
	} else {        //不平衡  右边深  左旋
		return leftRotate(root)

	}
}

console.log(isBalance(node2))

var newRoot = change(node2)
console.log(isBalance(newRoot))
console.log(newRoot)
